This invention relates to computer operation, and more particularly to a method of simulating the performance of a set-associative cache using a direct-mapped cache in a computer using a virtual memory.
As the speed of processors increases, the use of fast cache memory in computer systems becomes more important. For example, a high speed RISC processor of the type disclosed in my copending application Ser. No. 547,630, filed Jun. 29, 1990, may be constructed to operate at a CPU cycle time of 5-nsec, and execute an instruction during each cycle (due to the RISC concepts implemented). If the main memory has a cycle time of 300-nsec, it can be calculated that the CPU will spend 95% of its time waiting for memory, using cache hit rates that are now typical. To bring the memory performance more in line with the CPU, the cache memory is made hierarchical, providing primary, secondary, and, in some cases, third level caches, and of course the speed of the cache memories is increased as much as is economical. Nevertheless, the hit rate for the cache must be increased to achieve acceptable performance for these high-speed CPUs.
Cache memories are constructed in either direct-mapped architecture or N-way associative. A direct-mapped cache allows a given data item to be stored at only one place in the cache, so the hit rate is lower, but the advantage of a direct-mapped cache is that the circuitry is simple and very fast. An N-way associative cache allows a given data item to be stored at any of N different places in the cache, and this produces a higher hit rate than a direct-mapped cache of the same size. The higher hit rate of an N-way associative cache is a result of the increased flexibility of placement of information in the cache.
It would be desirable to be able to employ a direct-mapped cache in a high-performance computer system for the speed and simplicity of construction of this type of cache, but yet achieve higher cache hit rates as are inherent in N-way associative caches.